\documentclass[12pt]{article}

\usepackage[spanish]{babel}
\usepackage{amsfonts}
\usepackage{algorithm2e}
\usepackage{listings}
\lstset{ %
			language=Python,
			basicstyle=\footnotesize,
			numbers=left,
			stepnumber=1,
			numbersep=4pt,
			tabsize=2,
}


\title{Problema de Scheduling de streams}
\author{
        Ignacio Garay \\
                \and
        Ariel Liguori\\
        	\and
	Pablo Musumeci
}
\date{\today}



\begin{document}
\maketitle

\begin{abstract}
El presente es un an\'alisis sobre el problema de control de inventario con una aplicaci\'on de programaci\'on din\'amica.
\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introducci\'on}\label{intro}
El problema del control de inventario consta del problema que afronta 
una empresa para decidir en qu\'e momento ser\'ia \'optimo hacer el
pedido de compras tal que se cubra la demanda y se minimice el costo.
Debido a que es un problema que involucra un avance temporal, en el presente
se tomar\'a la hip\'otesis de que el tiempo es discretizable en alg\'un per\'iodo.
En nuestro caso, el problema ser\'a cuantizable en meses y el per\'iodo adoptado es el
de un a\~no.\\

\newpage
\section{Planteo}\label{planteo}
El planteo matem\'atico del problema es el siguiente:

La concesionaria tiene una cantidad $k$ de per\'iodos, en donde puede comprar una
cantidad $x_k$ de camiones. Se cuenta con un almacen en donde puede guardar camiones, 
lo cual modelizamos mediante la variable $x_k$ la cual representa la cantidad de
camiones que hay en el almacen en el per\'iodo k.

Existe una demanda la cual debemos cumplir, para eso debemos contar con esa cantidad
de camiones disponibles en ese per\'iodo (por disponibles nos referimos a la suma
de la cantidad de camiones en el almacen más la cantidad adquirida en dicho per\'iodo).
La cantidad de camiones que se puede guardar esta limitada por la capacidad 
del almacen, esto se ve reflejado en la siguiente ecuaci\'on:

\begin{equation}\label{..} x_k \le S\end{equation}

Se define el stock de cada mes como:

\begin{equation}\label{..} x_{k+1} = x_{k} + u_k - w_k \end{equation}

En donde $u_k$ representa la cantidad de camiones comprados, y $w_k$ la demanda
que se debe cumplir, ambas cantidades relacionadas a un per\'iodo $k$ en particular.\\

Almacenar un cami\'on en el dep\'osito tiene un costo asociado de valor $C$; mientras
que por cada orden de compra librada, tenemos un costo fijo (es decir, independiente
de la cantidad de camiones que se adquieran en dicha orden) a pagar.\\

El objetivo del algoritmo a desarrollar involucra determinar la \emph{asignaci\'on}
\'optima de la cantidad de camiones a comprar en cada mes, tal que se minizimen los
costos involucrados en las compras y almacenamiento de camiones; teniendo en cuenta
las restricciones propias del problema, como el límite de camiones que pueden estar
en el almacen.\\

\section{Algoritmos}\label{algoritmos}
\subsection{Algoritmo O(n log(n)}

\begin{algorithm}[H]

	\SetAlgoLined

	\KwData{streams, restriction}
	\KwResult{lista\_solucion }
	$t\leftarrow 0$\;
	$b\leftarrow 0$\;
	$set\_auxiliar\leftarrow Timsort(streams)$\;
	$set\_solucion\leftarrow Nuevo Set$\;
 	set\_auxiliar = streams.copia()\;
	\For{elemento de set\_auxiliar}{
		$t\leftarrow t+elemento.tiempo$\;
		$b\leftarrow b+elemento.bits$\;
		\If {$t * restriccion\leq b$}{
			return set\_vacio\;
		}
		set\_solucion.agregar(elemento)\;
	}
	return set\_solucion\;

\caption{Algoritmo de scheduling de \'orden O(n log n)}
\end{algorithm}

\subsection{Algoritmo O(n)}
\begin{algorithm}[H]

	\SetAlgoLined
	\KwData{streams, restriction}
	\KwResult{ set\_valido: bool }
	$t\leftarrow 0$\;
	$b\leftarrow 0$\;
	\For{elemento de set\_auxiliar}{
		$t\leftarrow t+elemento.tiempo$
		$b\leftarrow b+elemento.bits$
	}
	return $t * restriction \ge b$

 \caption{Algoritmo de scheduling de \'orden O(n)}
\end{algorithm}

\newpage

\section{An\'alisis}\label{analisis}
Como podemos ver, el primer algoritmo se encuentra acotado por la operaci\'on de mayor costo, que es el ordenamiento.
Debido a que el Timsort es un ordenamiento por comparaci\'on, su cota m\'axima es de n log n, siendo n la cantidad de streams. El resto de las operaciones son iterar sobre un set, operaciones aritm\'eticas y comparaciones tienen un tiempo de ejecuci\'on menor a n log n (n y 1 respectivamente).\\
Como se plante\'o en la seccion de Planteo, lo que tiene de interesante de la elecci\'on del algoritmo greedy y de la regla de decisi\'on es que la soluci\'on es una \'optima.\\
Otro tema importante a destacar que el algoritmo lo que hace es verificar si el set es v\'alido y si lo llega a ser, devuelve el set soluci\'on, obteniendo mucha m\'as informaci\'on del problema de la que me podr\'ia llegar a proveer el algoritmo lineal.\\
Con respecto al algoritmo lineal, se puede destacar que, debido a una regla de decisi\'on simple pero poderosa, se logra simplificar el problema. Aunque en el proceso se descarta mucha informaci\'on (como el \'orden de streams), a\'un podemos obtener una soluci\'on \'optima. El tiempo de ejecuci\'on del mismo queda acotado a la iteraci\'on sobre el set de streams. Este costo es n, siendo n la cantidad de elementos del set.\\
Como conclusi\'on importante se puede destacar que para reducir la cota algor\'itmica hubo que resignar la informaci\'on adicional que el algoritmo m\'as lento prove\'ia. Esto se puede entender debido a que la regla de decisi\'on del algoritmo lineal es en efecto mucho m\'as fuerte y restrictiva que la emplada para el otro algoritmo.\\
Es a destacar que se puede reducir la cota inferior del primer algoritmo, haciendo un primer recorrido del set e incorporando los elementos v\'alidos a mi set soluci\'on y los rechazados a un heap minimal. Si al final de la pasada quedan elementos pendientes, se procede a sacar todo elemento rechazado del heap minimal, agreg\'andolo al set soluci\'on. Si alg\'un elemento sacado del heap no puede ser incorporado al set soluci\'on, implica que el set no es un set v\'alido.

\newpage

\section{Ap\'endice: Timsort}\label{timsort}
El algoritmo de Timsort es un derivado del Mergesort. Entre algunas de las distinciones m\'as notables entra la capacidad
de reconocer patrones ordenados dentro de la lista. En vez de tomar particiones de un n\'umero fijo de elementos,
 particiona el espacio de la lista seg\'un los \'ordenes parciales que pueda llegar a tener adentro. Esto permite que en
 casos donde la lista contiene elementos ordenados de forma parcial o una lista pr\'acticamente ordenada salvo por elementos que distorcionan, se logre una forma de ordenar muy r\'apida. Se dice que el Timsort es un algoritmo adaptativo porque
se encuentra optimizado para casos de pocos elementos, cambiando a un insertionsort. El comportamiento del Timsort en el peor caso se encuentra en el que la entrada sea completamente random, sin ninguna clase de ordenamiento parcial. En ese
caso, el Timsort, luego de una primer pasada lineal para encontrar runs, decanta en un mergesort.\\
Esto se debe a que el Timsort tiene como invariante de que en la pila donde se almacenan los runs no pueda superar los 
$log(n)$ elementos. Para lograr esto, se pide como invariante que $tam_i <= 2 * tam_{i+1}$. Entonces de esta forma, en 
el peor de los casos, estar\'iamos haciendo $log(n)$ mezclas en tiempo $n$, debido a que la forma de mezclar es lineal.
En consecuencia, el algoritmo en el peor caso estar\'ia ordenando en $O(n*log(n))$.

\bibliographystyle{abbrv}
\bibliography{simple}

\newpage
\section{Anexo: implementaci\'on de los algoritmos en Python}\label{codigo}
\subsection{inventory.py}
\lstinputlisting{inventory.py}
\newpage
\end{document}
